
# ----------小步语义部分---------
class Number < Struct.new(:value)
end

class Add < Struct.new(:left, :right)
end

class Multiply < Struct.new(:left, :right)
end


class Number
    def to_s
        value.to_s
    end

    def inspect
        "<<#{self}>>"
    end
end

class Add
    def to_s
        "#{left} + #{right}"
    end

    def inspect
        "<<#{self}>>"
    end
end

class Multiply
    def to_s
        "#{left} * #{right}"
    end

    def inspect
        "<<#{self}>>"
    end
end

class Number
    def reducible?
        false
    end
end

class Add
    def reducible?
        true
    end
end

class Multiply
    def reducible?
        true
    end
end

class Add
    def reduce
        if left.reducible?
            Add.new(left.reduce, right)
        elsif right.reducible?
            Add.new(left, right.reduce)
        else
            Number.new(left.value + right.value)
        end
    end
end


class Multiply
    def reduce
        if left.reducible?
            Multiply.new(left.reduce, right)
        elsif right.reducible?
            Multiply.new(left, right.reduce)
        else
            Number.new(left.value * right.value)
        end
    end
end


class Machine < Struct.new(:expression)
    def step
        self.expression = expression.reduce
    end

    def run
        while expression.reducible?
            puts expression
            step
        end
        puts expression
    end
end


class Boolean < Struct.new(:value)
    def to_s
        value.to_s
    end

    def inspect
        "<<#{self}>>"
    end 

    def reducible?
        false
    end
end

class LessThan < Struct.new(:left, :right)
    def to_s
        "#{left} < #{right}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce
        if left.reducible?
            LessThan.new(left.reduce, right)
        elsif right.reducible?
            LessThan.new(left, right.reduce)
        else
            Boolean.new(left.value < right.value)
        end
    end
end

class Variable < Struct.new(:name)
    def to_s
        name.to_s
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end
end

class Variable
    def reduce(environment)
        environment[name]
    end
end

class Add
    def reduce(environment)
        if left.reducible?
            Add.new(left.reduce(environment), right)
        elsif right.reducible?
            Add.new(left, right.reduce(environment))
        else
            Number.new(left.value + right.value)
        end
    end
end

class Multiply
    def reduce(environment)
        if left.reducible?
            Multiply.new(left.reduce(environment), right)
        elsif right.reducible?
            Multiply.new(left, right.reduce(environment))
        else
            Number.new(left.value * right.value)
        end
    end
end 


class LessThan
    def reduce(environment)
        if left.reducible?
            LessThan.new(left.reduce(environment), right)
        elsif right.reducible?
            LessThan.new(left, right.reduce(environment))
        else
            Boolean.new(left.value < right.value)
        end
    end
end

Object.send(:remove_const, :Machine)    # 忘记原来的Machine 类

class Machine < Struct.new(:expression, :environment)
    def step
        self.expression = expression.reduce(environment)
    end

    def run
        while expression.reducible?
            puts expression
            step
        end

        puts expression
    end
end



class DoNothing # 1
    def to_s
        'do-nothing'
    end

    def inspect
        "<<#{self}>>"
    end

    def ==(other_statement)    # 2
        other_statement.instance_of?(DoNothing)
    end

    def reducible?
        false
    end
end

class Assign < Struct.new(:name, :expression)
    def to_s
        "#{name} = #{expression}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        if expression.reducible?
            [Assign.new(name, expression.reduce(environment)), environment]
            # 总结1
        else
            [DoNothing.new, environment.merge({name => expression})]
            # 总结2
        end
    end
end


Object.send(:remove_const, :Machine)   # 清空当前虚拟机
class Machine < Struct.new(:statement, :environment)
    def step
        self.statement, self.environment = statement.reduce(environment)
    end

    def run
        while statement.reducible?
            puts "#{statement}, #{environment}"
            step
        end

        puts "#{statement}, #{environment}"
    end
end


class If < Struct.new(:condition, :consequence, :alternative)
    def to_s
        "if(#{condition}) { #{ consequence } } else { #{alternative} } "
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment) 
        if condition.reducible?
            [If.new(condition.reduce(environment), consequence, alternative), environment]
        else
            case condition
            when Boolean.new(true)
                [consequence, environment]
            when Boolean.new(false)
                [alternative, environment]
            end
        end
    end
end


class Sequence < Struct.new(:first, :second)
    def to_s
        "#{first};#{second}"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        case first
        when DoNothing.new
            [second, environment]
        else
            reduced_first, reduced_environment = first.reduce(environment)
            [Sequence.new(reduced_first, second), reduced_environment]
        end
    end
end


class While < Struct.new(:condition, :body)
    def to_s
        "while (#{condition}) { #{body} }"
    end

    def inspect
        "<<#{self}>>"
    end

    def reducible?
        true
    end

    def reduce(environment)
        [If.new(condition, Sequence.new(body, self), DoNothing.new), environment]
    end
end

# ----------小步语义部分---------

# 小步语义的优势：能够把程序执行的复杂过程分成更小的片段进行解释和分析
# 但是缺点是不够直接：我们没有解释整个程序结构是如何工作的，只是展示了它是如何慢慢被规约的

# 完成的说明程序的执行过程，正是大步语义（big-step semantic）的依据

# 大步语义的思想：定义如何从一个表达式或者语句直接得到他的结果。

# 这里我们必须将程序的执行当做一个递归的过程，而非迭代的过程
# 大步语义就是说，为了对一个更大的表达式进行求值，我们必须对所有比它小的子表达式求值，然后把结果结合起来，就得到了答案


# 大步语义的规则描述了如何只对程序的抽象语法树访问一次，就计算出整个程序的结果
# 自然不需要类似小步语义中的Machine 类跟踪状态并反复规约了,我们只需要对语句和表达式定义一个evaluate 方法,并直接调用它

# 1. 表达式
# 大步语义中,每个表达式都能求值,单个数字本身也是表达式

# 数值和布尔值大步规则很简单:直接求值,就是本身
class Number
    def evaluate(environment)
        self
    end
end

class Boolean
    def evaluate(environment)
        self
    end
end

# 变量:在环境中查找变量名,并返回它的值
class Variable
    def evaluate(environment)
        environment[name]
    end
end


# 二元表达式
class Add
    def evaluate(environment)
        Number.new(left.evaluate(environment).value + right.evaluate(environment).value)
    end
end

class Multiply
    def evaluate(environment)
        Number.new(left.evaluate(environment).value * right.evaluate(environment).value)
    end
end


class LessThan
    def evaluate(environment)
        Boolean.new(left.evaluate(environment).value < right.evaluate(environment).value)
    end
end

puts Number.new(23).evaluate({})
# 23

num1 = Variable.new(:x).evaluate({x: Number.new(42)})
puts num1
# 42

result1 = LessThan.new(
    Add.new(Variable.new(:x), Number.new(2)),
    Variable.new(:y)
).evaluate({x: Number.new(2), y: Number.new(5)})
puts result1
# true

# 2. 语句
# 我们可以把大步语义的语句求值看成一个过程,这个过程总是把
# 一个语句和一个初始环境转换成一个最终的环境,并可以避免小步语义下对reduce 
# 产生的中间语句进行处理的复杂性

# 如会一个赋值语句按照大步的方法求值应该完整的对其表达式求值,并
# 返回一个包含结果值的更新了的环境
class Assign 
    def evaluate(environment)
        environment.merge({ name => expression.evaluate(environment) })
    end
end

class DoNothing
    def evaluate(environment)
        environment
    end
end

class If
    def evaluate(environment)
        case condition.evaluate(environment)
        when Boolean.new(true)
            consequence.evaluate(environment)
        when Boolean.new(false)
            consequence.evaluate(environment)
        end
    end 
end

class Sequence
    def evaluate(environment)
        second.evaluate(first.evaluate(environment))
    end
end

statement = Sequence.new(
    Assign.new(:x, Add.new(Number.new(1), Number.new(1))),
    Assign.new(:y, Add.new(Variable.new(:x), Number.new(3)))
)
puts statement
# x = 1 + 1;y = x + 3

puts statement.evaluate({})
# {:x=><<2>>, :y=><<5>>}